Neural Information Processing Systems http://nips.cc/

Inmany cases, increasing model capacity beyond the memory limit of a single acceleratorhas required developing special algorithms orinfrastructure. These solutions are often architecture-specific and do not transfer to other tasks.

We extend the Approximate-Proximal Point (aProx) family of model-based methods for solving stochastic convex optimization problems, including stochastic subgradient, proximal point, and bundle methods, to the minibatch setting. To do this, we propose two minibatched algorithms for which we prove a non-asymptotic upper bound on the rate of convergence, revealing a linear speedup in minibatch size. In contrast to standard stochastic gradient methods, these methods may have linear speedup in the minibatch setting even for non-smooth functions. Our algorithms maintain the desirable traits characteristic of the aProx family, such as robustness to initial step size choice. Additionally, we show improved convergence rates for interpolation problems, which (for example) gives a new parallelization strategy for alternating projections. We corroborate our theoretical results with extensive empirical testing, which demonstrates the gains provided by accurate modeling and minibatching.

Stochastic model-based methods have received increasing attention lately due to their appealing robustness to the stepsize selection and provable efficiency guarantee. We make two important extensions for improving model-based methods on stochastic weakly convex optimization. First, we propose new minibatch model-based methods by involving a set of samples to approximate the model function in each iteration. For the first time, we show that stochastic algorithms achieve linear speedup over the batch size even for non-smooth and non-convex (particularly, weakly convex) problems. To this end, we develop a novel sensitivity analysis of the proximal mapping involved in each algorithm iteration.

We introduce the Stochastic Asynchronous Proximal Alternating Linearized Minimization (SAPALM) method, a block coordinate stochastic proximal-gradient method for solving nonconvex, nonsmooth optimization problems. SAPALM is the first asynchronous parallel optimization method that provably converges on a large class of nonconvex, nonsmooth problems. We prove that SAPALM matches the best known rates of convergence --- among synchronous or asynchronous methods --- on this problem class. We provide upper bounds on the number of workers for which we can expect to see a linear speedup, which match the best bounds known for less complex problems, and show that in practice SAPALM achieves this linear speedup. We demonstrate state-of-the-art performance on several matrix factorization problems.

Neural Information Processing Systems http://nips.cc/

Neural Information Processing Systems http://nips.cc/

The analysis for Hogwild algorithm seems to be new as well, but I didn't go through the proof of that part. Significance: The new analysis supporting asynchronous update when features are sparse, will be an interesting message to the community. However as the assumption in Eq.(2) excludes many interesting problems, I don't think it will have a large impact. Q2: Please summarize your review in 1-2 sentences The paper suggests an analysis showing that the optimal bounds can be achieved by their suggested algorithm up to some factors, where the algorithm is claimed to have linear speedup with the number of cores and to benefit from the sparsity of input features. However, its applicability seems to be limited due to a rather restrictive assumption it is based upon, which makes the suggested method sensitive to the choices of stepsizes, and the other assumption on asynchronous update delays.

Neural Information Processing Systems http://nips.cc/